def uniquePaths(m, n):
    """
    :type m: int
    :type n: int
    :rtype: int
    """
    # 初始化格子
    dp = [[1] * n] * m
    for i in range(m):
        for j in range(n):
            if i - 1 >= 0 and j - 1 >= 0:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


print(uniquePaths(3, 3))
